package demo.hw;

/**
 * 题目描述
 * 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
 * 数据范围：0<=m<=10，1<=n<=10。
 * 本题含有多组样例输入。
 *
 * 输入描述：
 * 输入两个int整数
 *
 * 输出描述：
 * 输出结果，int型
 *
 * 示例1
 * 输入：
 * 7 3
 * 复制
 * 输出：
 * 8
 *
 * @author taqo
 * @date 2021/5/27
 */
public class _放苹果 {
    public static void main(String[] args) {
        int m = 7;//苹果
        int n = 3;//盘子

        System.out.println(count(m, n));
        System.out.println(count2(m, n));
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (i == 0 || j == 1) {
                    dp[i][j] = 1;
                } else if (j > i) {
                    dp[i][j] = dp[i][j];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
        }
        System.out.println(dp[m - 1][n - 1]);
    }

    private static int count2(int m, int n) {
        if (m == 0 || n ==1){
            return 1;
        } else if (n>m){
            return count2(m,m);
        } else {
            return count2(m,n-1)+count2(m-n,n);
        }
    }

    private static int count(int m, int n) {
        // m苹果 n盘子
        // 函数f(m,n)
        // 一个盘或者没有苹果
        if (n == 1 || m == 0) {
            return 1;
        } else if (n > m) {
            // 1.盘子比苹果多，那么肯定会有空盘子，空盘子有n-m个，最大可用的盘子(等于苹果数量)为m个
            return count(m, m);
        } else {
            // 2.苹果比盘子多，m>=n时，总算法=有盘子为空的放法+没盘子为空的放法
            // 每次空出一个盘子 count(m, n - 1)
            // 没有空盘子 多出来的苹果m-n，放到n个盘子 count(m - n, n)
            return count(m, n - 1) + count(m - n, n);
        }
    }
}
